#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2018 crane <crane@his-pc>
#
# Distributed under terms of the MIT license.

"""

"""


class Solution:
    def canJump(self, A):
        return self.can_greedy(A)

        # self.can_record = len(A) * [None]     # 表示 第i个元素是否能跳到终点(最终会求出是否所有的节点都能到达终点)
        # self.A = A
        # self.len = len(A)
        # return self.can_rec(0)

    def can_greedy(self, A):
        if not A:
            return False

        farthest = A[0]         # farthest变量表示第一个节点最远能到达的索引

        for i in range(1, len(A)):
            if farthest < i:
                return False
            move = A[i]
            farthest = max(farthest, i + move)

        # return farthest >= len(A)-1
        return True


    def can_rec(self, idx):
        # dynamic programming
        if self.can_record[idx] is not None:
            return self.can_record[idx]

        can = False
        max_jumps = self.A[idx]
        if max_jumps+ idx >= self.len-1:
            can = True
        else:
            # can = any([ self.can_rec(idx + jump) for jump in range(max_jumps, 0, -1)])    # 1 - max_jumps
            # 1 - max_jumps
            for jump in range(max_jumps, 0, -1):
                # 使用循环较 any的好处在于: 如果发现有一个分支返回Truea, 可以立即break循环
                if self.can_rec(idx + jump):
                    can = True
                    break

        self.can_record[idx] = can
        return can


def main():
    print("start main")
    s = Solution()
    # ret = s.canJump(A = [3,2,1,0,4])
    ret = s.canJump(A = [2,3,1,1,4])
    print(ret)

if __name__ == "__main__":
    main()
